◀ Prev · Parts · Full · Next ▶

To pick out a subsequence, first pick a binary function ϕ ϕ {\displaystyle \phi } , such that given any binary string x 1 : k {\displaystyle x_{1:k}} , it outputs either 0 or 1. If it outputs 1, then we add x k + 1 {\displaystyle x_{k+1}} to the subsequence, else we continue. In this definition, some admissible rules might abstain forever on some sequences, and thus fail to pick out an infinite subsequence. We only consider those that do pick an infinite subsequence.

Stated in another way, each infinite binary string is a coin-flip game, and an admissible rule is a way for a gambler to decide when to place bets. A collective is a coin-flip game where there is no way for one gambler to do better than another over the long run. That is, there is no gambling system that works for the game.

The definition generalizes from binary alphabet to countable alphabet:

• The frequency of each letter converges to a limit greater than zero.

• For any "admissible" rule, such that it picks out an infinite subsequence ( x m i ) i {\displaystyle (x_{m_{i}})_{i}} from the string, the frequency of each letter in the subsequence still converges to the same limit.

Usually the admissible rules are defined to be rules computable by a Turing machine, and we require p = 1 / 2 {\displaystyle p=1/2} . With this, we have the Mises–Wald–Church random sequences. This is not a restriction, since given a sequence with p = 1 / 2 {\displaystyle p=1/2} , we can construct random sequences with any other computable p ∈ ∈ ( 0 , 1 ) {\displaystyle p\in (0,1)} .cite-ref-1[1] (Here, "Church" refers to Alonzo Church, whose 1940 paper proposed using Turing-computable rules.cite-ref-2[2])

◀ Prev · Parts · Full · Next ▶